//
//  GetMaximumGold.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/22.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  1219:黄金矿工 中等

import UIKit

/*
 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

 为了使收益最大化，矿工需要按以下规则来开采黄金：

 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
 矿工每次可以从当前位置向上下左右四个方向走。
 每个单元格只能被开采（进入）一次。
 不得开采（进入）黄金数目为 0 的单元格。
 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
  

 示例 1：

 输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
 输出：24
 解释：
 [[0,6,0],
  [5,8,7],
  [0,9,0]]
 一种收集最多黄金的路线是：9 -> 8 -> 7。
 示例 2：

 输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
 输出：28
 解释：
 [[1,0,7],
  [2,0,6],
  [3,4,5],
  [0,3,0],
  [9,0,20]]
 一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
  

 提示：

 1 <= grid.length, grid[i].length <= 15
 0 <= grid[i][j] <= 100
 最多 25 个单元格中有黄金。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/path-with-maximum-gold
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
    [[3,31,23,3,15,20,12],
     [0,8,11,25,0,31,20],
     [39,30,16,11,2,29,34],
     [13,38,35,3,0,14,9]]
 
 
 */

class GetMaximumGold: NSObject {
    
    var pathArr:[[[Int]]] = []
    
    func getMaximumGold(_ grid: [[Int]]) -> Int {
        
        //记录可作为起点的坐标
        var originPointArr:[[Int]] = []

        //首先找到所有可能的起点
        for i in 0 ..< grid.count {
            for j in 0 ..< grid[i].count{
                if grid[i][j] != 0 {
                    originPointArr.append([i,j])
                }
            }
        }
        
        for point in originPointArr{
            self.dfs(point, grid, [])
        }
        
        var maxGoldNum = 0
        var bestPath:[[Int]] = []
        for index in 0 ..< pathArr.count{
            let arr = pathArr[index]
            //print(grid[arr[0]][arr[1]])
            
            print("\(arr)\n\n")
            
            var sumGold = 0
            for pathIndex in 0 ..< arr.count{
                let point = arr[pathIndex]
                sumGold = sumGold + grid[point[0]][point[1]]
            }
            
            if sumGold > maxGoldNum {
                maxGoldNum = sumGold
                bestPath = arr
            }
            
        }
            
        print("最佳金矿数量为\(maxGoldNum)--最佳路径数量为\(bestPath)")
        
        return maxGoldNum
    }
    
    
    func dfs(_ enterPoint:[Int], _ sourceGrid: [[Int]], _ tmpArr:[[Int]]){
        
        var sourceGrid = sourceGrid
        
        var arr = tmpArr
        
        //本条路径结束条件 四周都为0或墙壁
        
        let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
        let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
        let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
        let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
        
        if self.pointVaildCheck(enterPoint, sourceGrid) == false{
            return
        }
        
        if self.isEndPoint(enterPoint, sourceGrid){
            arr.append(enterPoint)
            //本条路径结束
            self.pathArr.append(arr)

            print("本条路径结束>>>>>>>>>>>>>>>>>>>>>>>>结束点：\(enterPoint[0])*\(enterPoint[1])")
            print("本条路径结束>>>>>>>>>完整路径为：\(arr)")
            return
        }
        
        //表示该点有金矿 可以继续探索
        print("路径被记录>>>\(enterPoint[0])*\(enterPoint[1])")
        arr.append(enterPoint)
        //readedArr.append(enterPoint)
        sourceGrid[enterPoint[0]][enterPoint[1]] = 0
        //上
        self.dfs(nextPointUp, sourceGrid, arr)
        
        //左
        self.dfs(nextPointLeft, sourceGrid, arr)
        
        //下
        self.dfs(nextPointDown, sourceGrid, arr)
        
        //右
        self.dfs(nextPointRight, sourceGrid, arr)
        
    }
    
    
    //本条路径结束条件 四周都为0或墙壁
    func isEndPoint(_ point:[Int], _ goldOre:[[Int]])->Bool{

        let upPoint = [point[0] - 1, point[1]]
        let leftPoint = [point[0], point[1] - 1]
        let downPoint = [point[0] + 1, point[1]]
        let rightPoint = [point[0], point[1] + 1]
        
        return  self.pointVaildCheck(upPoint, goldOre) == false &&
                self.pointVaildCheck(leftPoint, goldOre) == false &&
                self.pointVaildCheck(downPoint, goldOre) == false &&
                self.pointVaildCheck(rightPoint, goldOre) == false
    }
    
    func pointVaildCheck(_ point:[Int], _ goldOre:[[Int]])->Bool{
        var vaildCheck = true
        if  point[0] >= 0 && point[0] < goldOre.count &&
            point[1] >= 0 && point[1] < goldOre[0].count{
            
            //没有越界 判断金矿数
            if goldOre[point[0]][point[1]] == 0 {
                vaildCheck = false
            }
        }else{
            vaildCheck = false
        }
        return vaildCheck
    }
    
}




/*
     if enterPoint[0] == 0 && enterPoint[1] == 0 {
         //起点在0，0的位置  可以 右、下 两个方向查找查找
         print("1")
     }else if enterPoint[0] == 0 && enterPoint[1] == sourceGrid[0].count - 1{
         //起点在第一行末尾 可以 左、下 两个方向查找
         print("2")
     }else if enterPoint[0] == sourceGrid.count - 1 && enterPoint[1] == 0{
         //起点在第一列末尾 可以 上、右 两个方向查找
         print("3")
     }else if enterPoint[0] == sourceGrid.count - 1 && enterPoint[1] == sourceGrid[0].count - 1{
         //起点在右下角 可以 左、上 两个方向查找
         print("4")
     }else if enterPoint[0] == 0 && enterPoint[1] < sourceGrid[0].count - 1{
         //起点在第一行中间(不包括头尾) 可以 左、下、右 三个方向查找
         print("5")
     }else if enterPoint[0] < sourceGrid.count - 1 && enterPoint[1] == 0{
         //起点在第一列中间(不包括头尾) 可以 上、右、下 三个方向查找
         print("6")
     }else if enterPoint[0] == sourceGrid.count - 1 && enterPoint[1] < sourceGrid[0].count - 1{
         //起点在最后一行中间 可以 左、上、右 两个方向查找
         print("7")
     }else if enterPoint[0] < sourceGrid.count - 1 && enterPoint[1] == sourceGrid[0].count - 1{
         //起点在最后一列中间 可以 上、右 两个方向查找
         print("8")
     }
 */
